package someTestExcemple.huaweiOd.container.tree;

//华为OD机试 - 二叉树遍历 - 中序遍历（Java 2025 A卷 100分）
//https://blog.csdn.net/guorui_java/article/details/146327811
import java.util.*;
public class LDRTraversal {

    //全局变量，用于记录当前解析的位置
    private static int index = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        TreeNode treeRoot = buildTree(str);
        StringBuilder result = new StringBuilder();
        inorderTraversal(treeRoot,result);
        System.out.println(result.toString());

    }

    public static class TreeNode {
        char val; //节点值
        TreeNode left; //左节点
        TreeNode right; //右节点

        TreeNode(char value) {
            this.val = value;
        }
    }

    //a{b{d,e{g,h{,i}}},c{f}}
    // 构建二叉树的方法
    private static TreeNode buildTree(String s) {
        if (index >= s.length()) {
            return null;
        }
        // 获取当前节点的值
        char val = s.charAt(index++);
        TreeNode node = new TreeNode(val);

        // 如果遇到左大括号，说明有子节点
        if (index < s.length() && s.charAt(index) == '{') {
            index++; // 跳过左大括号
            // 构建左子树
            if (s.charAt(index) != ',') {
                //有左子树
                node.left = buildTree(s);
            }
            // 跳过逗号
            if (index < s.length() && s.charAt(index) == ',') {
                index++;
            }
            // 构建右子树
            if (index < s.length() && s.charAt(index) != '}') {
                node.right = buildTree(s);
            }
            index++; // 跳过右大括号
        }
        return node;
    }


    // 中序遍历二叉树的方法
    private static void inorderTraversal(TreeNode node, StringBuilder result) {
        if (node == null) {
            return;
        }
        // 遍历左子树
        inorderTraversal(node.left, result);
        // 访问根节点
        result.append(node.val);
        // 遍历右子树
        inorderTraversal(node.right, result);
    }
}
/**
 * a{b{d,e{g,h{,i}}},c{f}}
 * dbgehiafc
 */